
//Copyright 1997-2009 Syrinx Development, Inc.
//This file is part of the Syrinx Web Application Framework (SWAF).
// == BEGIN LICENSE ==
//
// Licensed under the terms of any of the following licenses at your
// choice:
//
//  - GNU General Public License Version 3 or later (the "GPL")
//    http://www.gnu.org/licenses/gpl.html
//
//  - GNU Lesser General Public License Version 3 or later (the "LGPL")
//    http://www.gnu.org/licenses/lgpl.html
//
//  - Mozilla Public License Version 1.1 or later (the "MPL")
//    http://www.mozilla.org/MPL/MPL-1.1.html
//
// == END LICENSE ==
using System;
using System.Collections;
using System.Diagnostics;
using System.Threading;
using System.Runtime.Serialization;


namespace Swaf.Container
{
	/// <summary>
	/// The BTree stores key/value pairs in instances of this class which
	/// serve as the main storage for elements added to the tree.
	/// </summary>
	[Serializable]
	public class BTreeEntry
	{
		protected IComparable m_key;
		protected object m_value;

		public BTreeEntry(IComparable key, object val)
		{
			m_key = key;
			m_value = val;
		}

		public IComparable Key {get{return m_key;}set{m_key = value;}}
		public object Value {get{return m_value;}set{m_value = value;}}
	}

	/// <summary>
	/// The one and only exception that will be thrown from the BTree.
	/// </summary>
	[Serializable]
	public class BTreeException : BaseException
	{
		public BTreeException(string msg)
			:base(msg)
		{
		}

		public BTreeException(string msg, Exception innerException)
			:base(msg, innerException)
		{
		}
		public BTreeException(System.Runtime.Serialization.SerializationInfo info, System.Runtime.Serialization.StreamingContext context) 
			: base(info, context)
		{
		}
	}

	/// <summary>
	/// Thread safe implementation of modified B+tree.
	/// </summary>
	/// <remarks>
	///	<h2>B+tree Implementation notes</h2>
	///<p>This class uses a single System.Threading.ReaderWriterLock to manage multi threaded
	///access.  This implementation uses a pesimistic write lock aproach where it locks at the B+Tree
	///level.  So when a write operation is happening to the tree, all readers complete,  all other
	///readers and writers block and the single write occurs.</p>
	///<p>This implements B-trees with several refinements. Most of them can be found
	///	in Knuth Vol 3, but some were developed to adapt to restrictions imposed
	///	by C++. First, a restatement of Knuth's properties that a B-tree must
	///	satisfy, assuming we make the enhancement he suggests in the paragraph
	///	at the bottom of page 476. Instead of storing null pointers to non-existent
	///	nodes (which Knuth calls the leaves) we utilize the space to store keys.
	///	Therefore, what Knuth calls level (l-1) is the bottom of our tree, and
	///	we call the nodes at this level LeafNodes. Other nodes are called InnerNodes.
	///	The other enhancement we have adopted is in the paragraph at the bottom of
	///	page 477: overflow control.</p>
	///	<p>
	///	The following are modifications of Knuth's properties on page 478:
	///	<p>
	///	<ol>
	///	<li>  Every InnerNode has at most Order keys, and at most Order+1 sub-trees.</li>
	///	<li>  Every LeafNode has at most 2*(Order+1) keys.</li>
	///	<li>  An InnerNode with k keys has k+1 sub-trees.</li>
	///	<li>  Every InnerNode that is not the root has at least InnerLowWaterMark keys.</li>
	///	<li>  Every LeafNode that is not the root has at least LeafLowWaterMark keys.</li>
	///	<li>  If the root is a LeafNode, it has at least one key.</li>
	///	<li>  If the root is an InnerNode, it has at least one key and two sub-trees.</li>
	///	<li>  All LeafNodes are the same distance from the root as all the other
	///		LeafNodes.</li>
	///	<li>  For InnerNode n with key n[i].key, then sub-tree n[i-1].tree contains
	///		all keys &lt; n[i].key, and sub-tree n[i].tree contains all keys
	///		&gt;= n[i].key.</li>
	///	<li>  Order is at least 3.</li>
	///	</ol>
	///	<p>
	///	The values of InnerLowWaterMark and LeafLowWaterMark may actually be set
	///	by the user when the tree is initialized, but currently they are set
	///	automatically to:
	///	<p><pre>
	///			InnerLowWaterMark = ceiling(Order/2)
	///			LeafLowWaterMark  = Order - 1
	///	</pre></p>
	///	<p>
	///	If the tree is only filled, then all the nodes will be at least 2/3 full.
	///	They will almost all be exactly 2/3 full if the elements are added to the
	///	tree in order (either increasing or decreasing). [Knuth says McCreight's
	///	experiments showed almost 100% memory utilization. I don't see how that
	///	can be given the algorithms that Knuth gives. McCreight must have used
	///	a different scheme for balancing. [No, he used a different scheme for
	///	splitting: he did a two-way split instead of the three way split as we do
	///	here. Which means that McCreight does better on insertion of ordered data,
	///	but we should do better on insertion of random data.]]</p>
	///	<p>
	///	It must also be noted that B-trees were designed for DISK access algorithms,
	///	not necessarily in-memory sorting, as we intend it to be used here. However,
	///	if the order is kept small (&lt; 6?) any inefficiency is negligible for
	///	in-memory sorting. Knuth points out that balanced trees are actually
	///	preferable for memory sorting. I'm not sure that I believe this, but
	///	it's interesting. Also, deleting elements from balanced binary trees, being
	///	beyond the scope of Knuth's book (p. 465), is beyond my scope. B-trees
	///	are good enough.</p>
	///	<p>
	///	A B-tree is declared to be of a certain ORDER (3 by default). This number
	///	determines the number of keys contained in any interior node of the tree.
	///	Each interior node will contain ORDER keys, and therefore ORDER+1 pointers
	///	to sub-trees. The keys are numbered and indexed 1 to ORDER while the
	///	pointers are numbered and indexed 0 to ORDER. The 0th ptr points to the
	///	sub-tree of all elements that are less than key[1]. Ptr[1] points to the
	///	sub-tree that contains all the elements greater than key[1] and less than
	///	key[2]. etc. The array of pointers and keys is allocated as ORDER+1
	///	pairs of keys and nodes, meaning that one key field (key[0]) is not used
	///	and therefore wasted.  Given that the number of interior nodes is
	///	small, that this waste allows fewer cases of special code, and that it
	///	is useful in certain of the methods, it was felt to be a worthwhile waste.</p>
	///	<p>
	///	The size of the exterior nodes (leaf nodes) does not need to be related to
	///	the size of the interior nodes at all. Since leaf nodes contain only
	///	keys, they may be as large or small as we like independent of the size
	///	of the interior nodes. For no particular reason other than it seems like
	///	a good idea, we will allocate 2*(ORDER+1) keys in each leaf node, and they
	///	will be numbered and indexed from 0 to 2*ORDER+1. It does have the advantage
	///	of keeping the size of the leaf and interior arrays the same, so that if we
	///	find allocation and de-allocation of these arrays expensive, we can modify
	///	their allocation to use a garbage ring, or something.</p>
	///	<p>
	///	Both of these numbers will be run-time constants associated with each tree
	///	(each tree at run-time can be of a different order). The variable "order"
	///	is the order of the tree, and the inclusive upper limit on the indices of
	///	the keys in the interior nodes.  The variable "order2" is the inclusive
	///	upper limit on the indices of the leaf nodes, and is designed</p>
	///	<p><pre>
	///		(1) to keep the sizes of the two kinds of nodes the same;
	///		(2) to keep the expressions involving the arrays of keys looking
	///			somewhat the same:   lower limit        upper limit
	///			for inner nodes:        1                order
	///			for leaf  nodes:        0                order2
	///			Remember that index 0 of the inner nodes is special.
	///	</pre></p>
	///	<p>
	///	Currently, order2 = 2*(order+1).</p>
	///	<p><pre>
	///	Picture: (also see Knuth Vol 3 pg 478)
	///
	///			+--+--+--+--+--+--...
	///			|  |  |  |  |  |
	///	parent---&gt;|  |     |     |
	///			|  |     |     |
	///			+*-+*-+*-+--+--+--...
	///				|  |  |
	///		+----+  |  +-----+
	///		|       +-----+  |
	///		V             |  V
	///		+----------+  |  +----------+
	///		|          |  |  |          |
	///	this-&gt;|          |  |  |          |&lt;--sib
	///		+----------+  |  +----------+
	///						V
	///						data
	///	</pre></p>
	///	<p>
	///	It is conceptually VERY convenient to think of the data as being the
	///	very first element of the sib node. Any primitive that tells sib to
	///	perform some action on n nodes should include this 'hidden' element.
	///	For InnerNodes, the hidden element has (physical) index 0 in the array,
	///	and in LeafNodes, the hidden element has (virtual) index -1 in the array.
	///	Therefore, there are two 'size' primitives for nodes:</p>
	///	<p><pre>
	///	Psize       - the physical size: how many elements are contained in the
	///				array in the node.
	///	Vsize       - the 'virtual' size; if the node is pointed to by
	///				element 0 of the parent node, then Vsize == Psize;
	///				otherwise the element in the parent item that points to this
	///				node 'belongs' to this node, and Vsize == Psize+1;
	///	</pre></p>
	///	<p>
	///	Parent nodes are always InnerNodes.</p>
	///	<p>
	///	These are the primitive operations on Nodes:</p>
	///	<p><pre>
	///	Append(elt)     - adds an element to the end of the array of elements in a
	///					node.  It must never be called where appending the element
	///					would fill the node.
	///	Split()         - divide a node in two, and create two new nodes.
	///	SplitWith(sib)  - create a third node between this node and the sib node,
	///					divvying up the elements of their arrays.
	///	PushLeft(n)     - move n elements into the left sibling
	///	PushRight(n)    - move n elements into the right sibling
	///	BalanceWithRight() - even up the number of elements in the two nodes.
	///	BalanceWithLeft()  - ditto
	///	</pre></p>
	///	<p>
	///	To allow this implementation of btrees to also be an implementation of
	///	sorted arrays/lists, the overhead is included to allow O(log n) access
	///	of elements by their rank (`give me the 5th largest element').
	///	Therefore, each Item keeps track of the number of keys in and below it
	///	in the tree (remember, each item's tree is all keys to the RIGHT of the
	///	item's own key).</p>
	///	<p><pre>
	///	[ [ &lt; 0 1 2 3 &gt; 4 &lt; 5 6 7 &gt; 8 &lt; 9 10 11 12 &gt; ] 13 [ &lt; 14 15 16 &gt; 17 &lt; 18 19 20 &gt; ] ]
	///	4  1 1 1 1   4   1 1 1   5   1  1  1  1      7  3   1  1  1    4    1  1  1
	///	</pre></p>
	/// </remarks>
	[Serializable]
	public class BTree : ISerializable
	{
		internal static int s_waitTimeout = 300;
		private int m_size;
		internal BTreeNode m_rootNode; //root node of btree
		private int m_order = 3; //the order of the tree (should be > 2)
		private int m_order2;            //order2+1 (assumes a memory access is
		//cheaper than a multiply and increment by one
		internal int m_innerLowWaterMark; //inner node low water mark
		internal int m_leafLowWaterMark;  //leaf low water mark
		internal int m_innerMaxIndex;     //maximum inner node index
		internal int m_leafMaxIndex;      //maximum leaf index

		private bool m_allowDuplicateKeys;

		[NonSerialized] ReaderWriterLock m_rootLock;

		/// <summary>
		/// initialize btree
		/// </summary>
		/// <param name="order"></param>
		private void Init(int order, bool allowDuplicateKeys)
		{
			// Initialize a B-tree.
			if (order < 3)
				throw new BTreeException("order must be at least 3");

			m_order  = order;
			m_order2 = 2 * (m_order+1);
			m_leafMaxIndex  = m_order2 - 1;     // m_items[0..m_order2-1]
			m_innerMaxIndex = m_order;          // m_items[1..m_order]

			// the low water marks trigger an exploration for balancing
			// or merging nodes.
			// When the size of a node falls below X, then it must be possible to
			// either balance this node with another node, or it must be possible
			// to merge this node with another node.
			// This can be guaranteed only if (this->Size() < (MaxSize()-1)/2).
			// == MaxSize() satisfies the above because we compare
			// lowwatermark with m_lastIndex
			m_leafLowWaterMark  = ((m_leafMaxIndex+1)-1) / 2 - 1;
			m_innerLowWaterMark = (m_order-1) / 2;

			m_allowDuplicateKeys = allowDuplicateKeys;
			m_rootLock = new ReaderWriterLock();
		}

		/// <summary>
		/// called when the root node is full
		/// </summary>
		internal void RootIsFull()
		{
			// The root of the tree is full. Create an InnerNode that
			// points to it, and then inform the InnerNode that it is full.

			BTreeNode oldroot = m_rootNode;
			m_rootNode = new BTreeInnerNode(null, this, oldroot);
			Debug.Assert(m_rootNode != null);
			oldroot.Split();
		}

		/// <summary>
		/// called when root is empty
		/// </summary>
		internal void RootIsEmpty()
		{
			// If root is empty clean up its space.

			if (m_rootNode.IsLeaf) 
			{
				BTreeLeafNode lroot = (BTreeLeafNode)m_rootNode;
				Debug.Assert(lroot.Psize() == 0);
				m_rootNode = null;
			} 
			else 
			{
				BTreeInnerNode iroot = (BTreeInnerNode)m_rootNode;
				Debug.Assert(iroot.Psize() == 0);
				m_rootNode = iroot.GetTree(0);
				m_rootNode.m_parentNode = null;
			}
		}

		protected internal void IncrCount() { ++m_size; }
		
		protected internal void DecrCount() { --m_size; }

		/*
		/// <summary>
		/// Adds the object to the tree; return the index in the tree at which
		/// the object was inserted. NOTE: other insertions and deletions may
		/// change this object's index.
		/// </summary>
		/// <param name="key"></param>
		/// <param name="obj"></param>
		/// <returns></returns>
		protected int IdxAdd(IComparable key, object obj)
		{
			// Add object and return its index in the tree.

			BTreeEntry item = new BTreeEntry(key, obj);
			int r;
			if (m_rootNode == null) {
				m_rootNode = new BTreeLeafNode(null, item, this);
				Debug.Assert(m_rootNode != null);
				IncrCount();
				r = 0;
			} else {
				BTreeNode loc = null;
				int idx = 0;
				if (m_rootNode.Found(key, ref loc, ref idx) != null) {
					// loc and idx are set to either where the object
					// was found, or where it should go in the Btree.
					// Nothing is here now, but later we might give the user
					// the ability to declare a B-tree as `unique elements only',
					// in which case we would handle an exception here.
					// cerr << "Multiple entry warning\n";
				} else {
					Debug.Assert(loc.IsLeaf);
				}
				if (loc.IsLeaf) {
					if (loc.m_parentNode == null)
						r = idx;
					else
						r = idx + loc.m_parentNode.FindRankUp(loc);
				} else {
					BTreeInnerNode iloc = (BTreeInnerNode)loc;
					r = iloc.FindRankUp(iloc.GetTree(idx));
				}
				loc.Add(item, idx);
			}
			Debug.Assert(r == Rank(key,false) || obj == (this)[r]);
			return r;
		}
		*/

		/// <summary>
		/// create a BTree of order n
		/// </summary>
		/// <param name="order"></param>
		public BTree(int order)
		{
			// Create a B-tree of certain order (by default 3).
			Init(order, true);
		}

		public BTree()
			:this(3)
		{
			//Intentionally left blank
		}

		public BTree(bool allowDuplicates)
			:this(3, allowDuplicates)
		{
			//Intentionally left blank
		}

		public BTree(int order, bool allowDuplicates)
		{
			Init(order, allowDuplicates);
		}

		public int Count {get{ return m_size; }}
		public object FindObject(IComparable key)
		{
			if (m_rootLock == null)
				m_rootLock = new ReaderWriterLock();
			m_rootLock.AcquireReaderLock(s_waitTimeout);
			try
			{
				// Find object using the objects Compare() member function.

				if (m_rootNode == null)
					return null;
				else 
				{
					BTreeNode loc = null;
					int idx = 0;
					return m_rootNode.Found(key, ref loc, ref idx);
				}
			}
			finally
			{
				m_rootLock.ReleaseReaderLock();
			}
		}

		public bool Contains(IComparable key)
		{
			if (m_rootLock == null)
				m_rootLock = new ReaderWriterLock();
			m_rootLock.AcquireReaderLock(s_waitTimeout);
			try
			{
				// Find object using the objects Compare() member function.

				if (m_rootNode == null)
					return false;
				else 
				{
					BTreeNode loc = null;
					int idx = 0;
					return m_rootNode.Contains(key, ref loc, ref idx);
				}
			}
			finally
			{
				m_rootLock.ReleaseReaderLock();
			}
		}

		public BTreeIterator MakeIterator(bool moveForward)
		{
			// Returns a B-tree iterator.
			return new BTreeIterator(this, moveForward);
		}

		public void Add(IComparable key, object obj)
		{
			m_rootLock.AcquireWriterLock(s_waitTimeout);
			try
			{
				//validateAllParentage();

				if (key == null)
					throw new BTreeException("Cannot use null as key value");

				if (m_rootNode == null) 
				{
					m_rootNode = new BTreeLeafNode(null, new BTreeEntry(key,obj), this);
					Debug.Assert(m_rootNode != null);
					IncrCount();
				}
				else 
				{
					BTreeNode loc = null;
					int idx = 0;
					bool foundDup = m_rootNode.Contains(key, ref loc, ref idx);
					Debug.Assert(loc != null);
					if(!m_allowDuplicateKeys && foundDup)
						loc.UpdateValue(idx, obj);
					else
						loc.Add(new BTreeEntry(key,obj), idx, false);
				}

				//validateAllParentage();
			}
			finally
			{
				m_rootLock.ReleaseWriterLock();
			}
		}

		internal void validateAllParentage()
		{
			if(m_rootNode is BTreeInnerNode)
				validateNodeParentage((BTreeInnerNode)m_rootNode);
		}
		internal void validateNodeParentage(BTreeInnerNode node)
		{
			for(int x = 0; x <= node.m_lastIndex; ++x)
				if(node.m_items[x].m_parentTree is BTreeInnerNode)
				{
					((BTreeInnerNode)node.m_items[x].m_parentTree).validateParentage();
					validateNodeParentage((BTreeInnerNode)node.m_items[x].m_parentTree);
				}
		}

		public object Remove(IComparable key)
		{
			m_rootLock.AcquireWriterLock(s_waitTimeout);
			try
			{
				// Remove an object from the tree.

				if (m_rootNode == null)
					return null;

				BTreeNode loc = null;
				int idx = 0;
				object ob = m_rootNode.Found(key, ref loc, ref idx);
				if (ob == null)
					return null;

				Debug.Assert(loc != null);
				loc.Remove(idx);
				return ob;
			}
			finally
			{
				m_rootLock.ReleaseWriterLock();
			}
		}

		public object At(int idx)
		{
			m_rootLock.AcquireReaderLock(s_waitTimeout);
			try
			{
				return m_rootNode[idx];
			}
			finally
			{
				m_rootLock.ReleaseReaderLock();
			}
		}

		public object First()
		{
			m_rootLock.AcquireReaderLock(s_waitTimeout);
			try
			{
				return m_rootNode[0];
			}
			finally
			{
				m_rootLock.ReleaseReaderLock();
			}
		}

		public object Last()
		{
			m_rootLock.AcquireReaderLock(s_waitTimeout);
			try
			{
				return m_rootNode[m_size-1];
			}
			finally
			{
				m_rootLock.ReleaseReaderLock();
			}
		}

		public int Order() { return m_order; }
		public BTreeEntry this[int i]
		{
			get
			{
				m_rootLock.AcquireReaderLock(s_waitTimeout);
				try
				{
					return m_rootNode[i];
				}
				finally
				{
					m_rootLock.ReleaseReaderLock();
				}
			}
		}

		public int Rank(IComparable key, bool useClosestMatch)
		{
			m_rootLock.AcquireReaderLock(s_waitTimeout);
			try
			{
				// Returns the rank of the object in the tree.

				if (m_rootNode == null)
					return -1;
				else
					return m_rootNode.FindRank(key, useClosestMatch);
			}
			finally
			{
				m_rootLock.ReleaseReaderLock();
			}
		}

		public BTree(System.Runtime.Serialization.SerializationInfo info, StreamingContext context)
		{
			m_size = info.GetInt32("s");
			Init(info.GetInt32("o"), info.GetBoolean("d"));
			m_rootNode = (BTreeNode)info.GetValue("r", typeof(BTreeNode));
		}
		#region ISerializable Members

		public void GetObjectData(System.Runtime.Serialization.SerializationInfo info, StreamingContext context)
		{
			info.AddValue("s", m_size);
			info.AddValue("o", m_order);
			info.AddValue("d", m_allowDuplicateKeys);
			info.AddValue("r", m_rootNode);
		}

		#endregion
	}

	/// <summary>
	/// The parent class for the inner and leaf node types used in the BTree.
	/// </summary>
	[Serializable]
	abstract class BTreeNode
	{
		internal int m_lastIndex;   // for inner node 1 <= m_lastIndex <= m_innerMaxIndex
		// for leaf node  1 <= m_lastIndex <= m_leafMaxIndex
		// (m_lastIndex==0 only temporarily while the tree is being
		// updated)

		internal BTreeInnerNode m_parentNode;   // a parent is always an inner node (or 0 for the root)
		protected BTree m_parentTree;     // the tree of which this node is a part

		public abstract bool IsLeaf{get;}

		public BTreeNode(BTreeInnerNode p, BTree t)
		{
			// Create a B-tree node.
			m_lastIndex   = -1;
			m_parentNode = p;
			if (p == null) 
			{
				Debug.Assert(t != null);
				m_parentTree = t;
			} 
			else
				m_parentTree = p.m_parentTree;
		}

		public void UpdateValue(int idx, object val)
		{
			BTreeEntry entry = GetKey(idx);
			entry.Value = val;
		}

		public abstract void Add(BTreeEntry obj, int index);
		public abstract void Add(BTreeEntry obj, int index, bool replaceAtIndex);
		public virtual BTree GetParentTree() {return m_parentTree;}
		public abstract void Remove(int index);
		public abstract BTreeEntry GetKey(int index);

		public abstract BTreeEntry this[int i]{get;}
		public abstract object Found(IComparable key, ref BTreeNode which, ref int where);
		public abstract bool Contains(IComparable key, ref BTreeNode which, ref int where);

		public abstract int FindRank(IComparable key, bool useClosestMatch);
		public abstract int Count(); // # keys in or below this node

		public abstract BTreeLeafNode FirstLeafNode();
		public abstract BTreeLeafNode LastLeafNode();

		public abstract void Split();
	}

	[Serializable]
	class BTreeItem
	{
		internal int m_numKeysInTree = 0;   // number of keys in BTree
		internal BTreeEntry m_key = null;             // key
		internal BTreeNode m_parentTree = null;            //! sub-tree

		public BTreeItem()
		{
			//Intentionally left blank
		}

		public BTreeItem(BTreeItem item)
		{
			this.m_numKeysInTree = item.m_numKeysInTree;
			this.m_key = item.m_key;
			this.m_parentTree = item.m_parentTree;
		}

		public BTreeItem(BTreeNode n, BTreeEntry obj)
		{
			// Create an item to be stored in the tree. An item contains a counter
			// of the number of keys (i.e. objects) in the node. A pointer to the
			// node and a pointer to the object being stored.

			m_numKeysInTree = n.Count()+1;
			m_parentTree = n;
			m_key  = obj;
		}

		public void AssignFrom(BTreeItem item)
		{
			this.m_numKeysInTree = item.m_numKeysInTree;
			this.m_key = item.m_key;
			this.m_parentTree = item.m_parentTree;
		}

	}

	[Serializable]
	class BTreeInnerNode : BTreeNode
	{
		internal BTreeItem[] m_items;   // actually m_items[MaxIndex()+1] is desired

		public override bool IsLeaf{get{return false;}}

		public BTreeInnerNode(BTreeInnerNode parent, BTree tree)
			:base(parent, tree)
		{
			// Create a B-tree innernode.

			int index = MaxIndex() + 1;
			m_items = new BTreeItem[index];
			for(int x = 0; x < index; ++x)
				m_items[x] = new BTreeItem();
		
		}

		public BTreeInnerNode(BTreeInnerNode parent, BTree tree, BTreeNode oldroot)
			:base(parent, tree)
		{
			// Called only by TBtree to initialize the BTreeInnerNode that is
			// about to become the root.

			m_items = new BTreeItem[MaxIndex()+1];
			for(int x = 0; x < m_items.Length; ++x)
				m_items[x] = new BTreeItem();
			Append(null, oldroot);
		}

		public override void Add(BTreeEntry obj, int idx)
		{
			// This is called only from TBtree::Add().

			Debug.Assert(idx >= 1);
			BTreeLeafNode ln = GetTree(idx-1).LastLeafNode();
			validateParentage();
			ln.Add(obj, ln.m_lastIndex+1);
			//this.m_parentTree.validateAllParentage();
		}
		public override void Add(BTreeEntry obj, int idx, bool replaceAtIndex)
		{
			// This is called only from TBtree::Add().
			Debug.Assert(idx >= 1);
			BTreeLeafNode ln = GetTree(idx-1).LastLeafNode();
			validateParentage();
			ln.Add(obj, ln.m_lastIndex+1, replaceAtIndex);
			//this.m_parentTree.validateAllParentage();
		}

		public void Add(BTreeItem itm, int idx)
		{
			AddElt(itm, idx);
			if (IsFull())
				InformParent();
		}

		public void Add(int at, BTreeEntry obj, BTreeNode n)
		{
			BTreeItem newitem = new BTreeItem(n, obj);
			Add(newitem, at);
		}

		public void AddElt(BTreeItem itm, int at)
		{
			Debug.Assert(0 <= at && at <= m_lastIndex+1);
			Debug.Assert(m_lastIndex < MaxIndex());
			for (int i = m_lastIndex+1; i > at ; --i)
			{
				m_items[i] = new BTreeItem(GetItem(i-1));
				//BTreeItem item = GetItem(i);
				//if(item != null)
				//	item.AssignFrom(GetItem(i-1));
			}
			SetItem(at, itm);
			m_lastIndex++;
		}

		internal void validateParentage()
		{
			for(int p = 0; p <= this.m_lastIndex; ++p)
			{
				if(m_items[p].m_parentTree != null)
					Debug.Assert(m_items[p].m_parentTree.m_parentNode == this);
			}
		}
		public void AddElt(int at, BTreeEntry obj, BTreeNode n)
		{
			BTreeItem newitem = new BTreeItem(n, obj);
			AddElt(newitem, at);
		}

		public override void Remove(int idx)
		{
			Debug.Assert(idx >= 1 && idx <= m_lastIndex);
			BTreeLeafNode lf = GetTree(idx).FirstLeafNode();
			SetKey(idx, lf.m_items[0]);
			lf.RemoveItem(0);
		}

		public void RemoveItem(int idx)
		{
			Debug.Assert(idx >= 1 && idx <= m_lastIndex);
			for (int to = idx; to < m_lastIndex; ++to)
				m_items[to] = m_items[to+1];
			--m_lastIndex;
			if (IsLow()) 
			{
				if (m_parentNode == null) 
				{
					// then this is the root; when only one child, make the child the root
					if (Psize() == 0)
						m_parentTree.RootIsEmpty();
				} 
				else
					m_parentNode.IsLow(this);
			}
		}


		public override BTreeEntry this[int idx]
		{
			get
			{
				for (int j = 0; j <= m_lastIndex; j++) 
				{
					int r;
					if (idx < (r = GetCount(j)))
						return GetTree(j)[idx];
					if (idx == r) 
					{
						if (j == m_lastIndex) 
						{
							throw new BTreeException("should not happen");
						} 
						else
							return GetKey(j+1);
					}
					idx -= r+1; // +1 because of the key in the node
				}
				throw new BTreeException("should not happen, 0 returned");
			}
		}

		public override object Found(IComparable key, ref BTreeNode which, ref int where)
		{
			//this.m_parentTree.validateAllParentage();
			
			// Recursively look for WHAT starting in the current node.
			for (int i = 1 ; i <= m_lastIndex; ++i) 
			{
				BTreeEntry entry = GetKey(i);
				if(entry != null)
				{
					int cmp = entry.Key.CompareTo(key);
					if (cmp == 0) 
					{
						// then could go in either m_items[i].m_parentTree or m_items[i-1].m_parentTree
						// should go in one with the most room, but that's kinda
						// hard to calculate, so we'll stick it in m_items[i].m_parentTree
						which = this;
						where = i;
						return GetKey(i).Value;
					}
					if (cmp > 0)
						return GetTree(i-1).Found(key, ref which, ref where);
				}
			}
			//this.m_parentTree.validateAllParentage();
			// key > this[m_lastIndex].m_key.Key, so recurse on last m_items.m_parentTree
			return GetTree(m_lastIndex).Found(key, ref which, ref where);
		}

		public override bool Contains(IComparable key, ref BTreeNode which, ref int where)
		{
			//this.m_parentTree.validateAllParentage();
			
			// Recursively look for WHAT starting in the current node.
			for (int i = 1 ; i <= m_lastIndex; ++i) 
			{
				BTreeEntry entry = GetKey(i);
				if(entry != null)
				{
					int cmp = entry.Key.CompareTo(key);
					if (cmp == 0) 
					{
						// then could go in either m_items[i].m_parentTree or m_items[i-1].m_parentTree
						// should go in one with the most room, but that's kinda
						// hard to calculate, so we'll stick it in m_items[i].m_parentTree
						which = this;
						where = i;
						return true;
					}
					if (cmp > 0)
						return GetTree(i-1).Contains(key, ref which, ref where);
				}
			}
			//this.m_parentTree.validateAllParentage();
			// key > this[m_lastIndex].m_key.Key, so recurse on last m_items.m_parentTree
			return GetTree(m_lastIndex).Contains(key, ref which, ref where);
		}

		public int Count(int idx)
		{
			return GetCount(idx);
		}

		public override int Count()
		{
			int sum = 0;
			for (int i = 0; i <= m_lastIndex; ++i)
				sum += GetCount(i);
			return sum + Psize();
		}

		public void SetTree(int i, BTreeNode node) 
		{
			m_items[i].m_parentTree = node; 
			node.m_parentNode = this; 
		}

		public void SetKey(int i, BTreeEntry obj) { m_items[i].m_key = obj; }

		public void SetItem(int i, BTreeItem itm) { m_items[i] = itm; itm.m_parentTree.m_parentNode = this; }

		public void SetItem(int i, BTreeEntry obj, BTreeNode node) { SetTree(i, node); SetKey(i, obj); }

		public int  GetCount(int i)
		{
			Debug.Assert(i >= 0 && i <= m_lastIndex);
			return m_items[i].m_numKeysInTree;
		}

		public void SetCount(int i, int r)
		{
			m_items[i].m_numKeysInTree = r;
		}

		/// <summary>
		/// Had default value for n=1
		/// </summary>
		/// <param name="i"></param>
		/// <param name="n"></param>
		/// <returns></returns>
		public int  IncCount(int i, int n)
		{
			return m_items[i].m_numKeysInTree += n;
		}

		/// <summary>
		/// Had default value for n=1
		/// </summary>
		/// <param name="i"></param>
		/// <param name="n"></param>
		/// <returns></returns>
		public int DecCount(int i, int n)
		{
			return m_items[i].m_numKeysInTree -= n;
		}

		public override int FindRank(IComparable key, bool useClosestMatch)
		{
			// Recursively look for WHAT starting in the current node.
			int rankIndex = -1;
			if (key.CompareTo(GetKey(1).Key) < 0)
				return GetTree(0).FindRank(key, useClosestMatch);
			int sum = GetCount(0);
			for (int i = 1; i < m_lastIndex; ++i) 
			{
				if (key.CompareTo(GetKey(i).Key) == 0)
					return sum;
				++sum;
				if (key.CompareTo(GetKey(i+1).Key) < 0)
				{
					rankIndex = GetTree(i).FindRank(key, useClosestMatch);
					return rankIndex==-1?rankIndex:sum + rankIndex;
				}
				sum += GetCount(i);
			}
			if (key.CompareTo(GetKey(m_lastIndex).Key) == 0)
				return sum;
			++sum;
			// key > GetKey(m_lastIndex).Key, so recurse on last m_items.m_parentTree
			rankIndex = GetTree(m_lastIndex).FindRank(key, useClosestMatch);
			return rankIndex==-1?rankIndex:sum + rankIndex;
		}

		public int FindRankUp(BTreeNode obj)
		{
			// FindRankUp is FindRank in reverse.
			// Whereas FindRank looks for the object and computes the rank
			// along the way while walking DOWN the tree, FindRankUp already
			// knows where the object is and has to walk UP the tree from the
			// object to compute the rank.

			int l   = IndexOf(obj);
			int sum = 0;
			for (int i = 0; i < l; ++i)
				sum += GetCount(i);
			return sum + l + (m_parentNode == null ? 0 : m_parentNode.FindRankUp(this));
		}

		public BTreeNode GetTree(int i)  { return m_items[i].m_parentTree; }

		public override BTreeEntry GetKey(int i)  { return m_items[i].m_key; }

		public BTreeItem GetItem(int i)  { return m_items[i]; }

		public int IndexOf(BTreeNode n)
		{
			// Returns a number in the range 0 to this->m_lastIndex
			// 0 is returned if THAT == m_parentTree[0].

			for (int i = 0; i <= m_lastIndex; ++i)
				if(GetTree(i) == n)
					return i;
			return 0;
		}

		public void IncrCount(BTreeNode that)
		{
			// THAT is a child of THIS that has just grown by 1.

			int i = IndexOf(that);
			++m_items[i].m_numKeysInTree;
			if (m_parentNode != null)
				m_parentNode.IncrCount(this);
			else
				m_parentTree.IncrCount();
		}

		public void DecrCount(BTreeNode that)
		{
			// THAT is a child of THIS that has just shrunk by 1.

			int i = IndexOf(that);
			--m_items[i].m_numKeysInTree;
			if (m_parentNode != null)
				m_parentNode.DecrCount(this);
			else
				m_parentTree.DecrCount();
		}

		public override BTreeLeafNode FirstLeafNode()
		{
			return GetTree(0).FirstLeafNode();
		}

		public override BTreeLeafNode LastLeafNode()
		{
			return GetTree(m_lastIndex).LastLeafNode();
		}

		public void InformParent()
		{
			if (m_parentNode == null) 
			{
				// then this is the root of the tree and needs to be split
				// inform the btree.
				Debug.Assert(m_parentTree.m_rootNode == this);
				m_parentTree.RootIsFull();
			} 
			else
				m_parentNode.IsFull(this);
		}

		public override void Split()
		{
			//this.m_parentTree.validateAllParentage();
			// This function is called only when THIS is the only descendent
			// of the root node, and THIS needs to be split.
			// Assumes that idx of THIS in m_parentNode is 0.

			BTreeInnerNode newnode = new BTreeInnerNode(m_parentNode,null);
			m_parentNode.Append(GetKey(m_lastIndex), newnode);
			newnode.AppendFrom(this, m_lastIndex, m_lastIndex);
			--m_lastIndex;
			m_parentNode.IncCount(1, newnode.GetCount(0));
			m_parentNode.DecCount(0, newnode.GetCount(0));
			BalanceWithRight(newnode, 1);
			//this.m_parentTree.validateAllParentage();
		}

		/// <summary>
		/// 
		/// </summary>
		/// <remarks>
		/// THIS and SIB are too full; create a NEWNODE, and balance
		/// the number of keys between the three of them.
		///
		/// picture: (also see Knuth Vol 3 pg 478)
		///               keyidx keyidx+1
		///                +--+--+--+--+--+--...
		///                |  |  |  |  |  |
		/// m_parentNode-->|  |     |     |
		///                |  |     |     |
		///                +*-+*-+*-+--+--+--...
		///                 |  |  |
		///            +----+  |  +-----+
		///            |       +-----+  |
		///            V             |  V
		///            +----------+  |  +----------+
		///            |          |  |  |          |
		///     this-->|          |  |  |          |<--sib
		///            +----------+  |  +----------+
		///                          V
		///                        data
		///
		/// keyidx is the index of where the sibling is, and where the
		/// newly created node will be recorded (sibling will be moved to
		/// keyidx+1)
		/// </remarks>
		/// <param name="r"></param>
		/// <param name="idx"></param>
		public void SplitWith(BTreeInnerNode rightsib, int keyidx)
		{
			//m_parentTree.validateAllParentage();
			Debug.Assert(keyidx > 0 && keyidx <= m_parentNode.m_lastIndex);

			rightsib.SetKey(0, m_parentNode.GetKey(keyidx));
			int Count = Psize() + rightsib.Vsize();
			int newSizeThis = Count / 3;
			int newSizeNew = (Count - newSizeThis) / 2;
			int newSizeSib = (Count - newSizeThis - newSizeNew);
			int noFromThis = Psize() - newSizeThis;
			int noFromSib = rightsib.Vsize() - newSizeSib;

			// because of their smaller size, this BTreeInnerNode may not have to
			// give up any elements to the new node.  I.e., noFromThis == 0.
			// This will not happen for BTreeLeafNodes.
			// We handle this by pulling an item from the rightsib.
			Debug.Assert(noFromThis >= 0);
			Debug.Assert(noFromSib >= 1);

			BTreeInnerNode newNode = new BTreeInnerNode(m_parentNode,null);
			if(noFromThis > 0) 
			{
				newNode.Append(GetItem(m_lastIndex));
				m_parentNode.AddElt(keyidx, GetKey(m_lastIndex--), newNode);
				if (noFromThis > 2)
					this.PushRight(noFromThis-1, newNode, keyidx);
				rightsib.PushLeft(noFromSib, newNode, keyidx+1);
			} 
			else 
			{
				// pull an element from the rightsib
				newNode.Append(rightsib.GetItem(0));
				m_parentNode.AddElt(keyidx+1, rightsib.GetKey(1), rightsib);
				rightsib.ShiftLeft(1);
				m_parentNode.SetTree(keyidx, newNode);
				rightsib.PushLeft(noFromSib-1, newNode, keyidx+1);
			}
			m_parentNode.SetCount(keyidx-1, this.Count());
			m_parentNode.SetCount(keyidx, newNode.Count());
			m_parentNode.SetCount(keyidx+1, rightsib.Count());
			if (m_parentNode.IsFull())
				m_parentNode.InformParent();
			//m_parentTree.validateAllParentage();
		}

		public void MergeWithRight(BTreeInnerNode rightsib, int pidx)
		{
			Debug.Assert(Psize() + rightsib.Vsize() < MaxIndex());
			if (rightsib.Psize() > 0)
				rightsib.PushLeft(rightsib.Psize(), this, pidx);
			rightsib.SetKey(0, m_parentNode.GetKey(pidx));
			AppendFrom(rightsib, 0, 0);
			m_parentNode.IncCount(pidx-1, rightsib.GetCount(0)+1);
			m_parentNode.RemoveItem(pidx);
		}

		public void BalanceWithLeft(BTreeInnerNode leftsib, int pidx)
		{
			// THIS has more than LEFTSIB. Move some item from THIS to LEFTSIB.
			// PIDX is the index of the parent item that will change when keys
			// are moved.

			Debug.Assert(Vsize() >= leftsib.Psize());
			Debug.Assert(m_parentNode.GetTree(pidx) == this);
			int newThisSize = (Vsize() + leftsib.Psize())/2;
			int noFromThis = Psize() - newThisSize;
			PushLeft(noFromThis, leftsib, pidx);
		}

		public void BalanceWithRight(BTreeInnerNode rightsib, int pidx)
		{
			// THIS has more than RIGHTSIB. Move some items from THIS to RIGHTSIB.
			// PIDX is the index of the parent item that will change when keys
			// are moved.

			Debug.Assert(Psize() >= rightsib.Vsize());
			Debug.Assert(m_parentNode.GetTree(pidx) == rightsib);
			int newThisSize = (Psize() + rightsib.Vsize())/2;
			int noFromThis = Psize() - newThisSize;
			PushRight(noFromThis, rightsib, pidx);
		}

		public void BalanceWith(BTreeInnerNode rightsib, int pindx)
		{
			// PINDX is the index of the parent item whose key will change when
			// keys are shifted from one InnerNode to the other.

			if (Psize() < rightsib.Vsize())
				rightsib.BalanceWithLeft(this, pindx);
			else
				BalanceWithRight(rightsib, pindx);
		}

		public void PushLeft(int noFromThis, BTreeInnerNode leftsib, int pidx)
		{
			// noFromThis==1 => moves the parent item into the leftsib,
			// and the first item in this's array into the parent item.
			//m_parentTree.validateAllParentage();
			Debug.Assert(m_parentNode.GetTree(pidx) == this);
			Debug.Assert(noFromThis > 0 && noFromThis <= Psize());
			Debug.Assert(noFromThis + leftsib.Psize() < MaxPsize());
			SetKey(0, m_parentNode.GetKey(pidx)); // makes AppendFrom's job easier
			//m_parentTree.validateAllParentage();
			leftsib.AppendFrom(this, 0, noFromThis-1);
			//m_parentTree.validateAllParentage();
			ShiftLeft(noFromThis);
			//m_parentTree.validateAllParentage();
			m_parentNode.SetKey(pidx, GetKey(0));
			m_parentNode.SetCount(pidx-1, leftsib.Count());
			m_parentNode.SetCount(pidx, Count());
			//m_parentTree.validateAllParentage();
		}

		public void PushRight(int noFromThis, BTreeInnerNode rightsib, int pidx)
		{
			Debug.Assert(noFromThis > 0 && noFromThis <= Psize());
			Debug.Assert(noFromThis + rightsib.Psize() < rightsib.MaxPsize());
			Debug.Assert(m_parentNode.GetTree(pidx) == rightsib);
			//
			// The operation is three steps:
			//  Step I.   Make room for the incoming keys in RIGHTSIB.
			//  Step II.  Move the items from THIS into RIGHTSIB.
			//  Step III. Update the length of THIS.
			//
			// Step I. Make space for noFromThis items
			//
			int start = m_lastIndex - noFromThis + 1;
			int tgt, src;
			tgt = rightsib.m_lastIndex + noFromThis;
			src = rightsib.m_lastIndex;
			rightsib.m_lastIndex = tgt;
			rightsib.SetKey(0, m_parentNode.GetKey(pidx));
			IncCount(0,1);
			while (src >= 0) 
			{
				// do this kind of assignment on BTreeInnerNode items only when
				// the parent fields of the moved items do not change, as they
				// don't here.
				// Otherwise, use SetItem so the parents are updated appropriately.
				rightsib.m_items[tgt--] = new BTreeItem(rightsib.GetItem(src--));
			}

			// Step II. Move the items from THIS into RIGHTSIB
			for (int i = m_lastIndex; i >= start; --i) 
			{
				// this is the kind of assignment to use when parents change
				rightsib.SetItem(tgt--, GetItem(i));
			}
			m_parentNode.SetKey(pidx, rightsib.GetKey(0));
			DecCount(0,1);
			Debug.Assert(tgt == -1);

			// Step III.
			m_lastIndex -= noFromThis;

			// Step VI.  update Count
			m_parentNode.SetCount(pidx-1, Count());
			m_parentNode.SetCount(pidx, rightsib.Count());
		}

		public void AppendFrom(BTreeInnerNode src, int start, int stop)
		{
			// This should never create a full node that is, it is not used
			// anywhere where THIS could possibly be near full.

			if (start > stop)
				return;
			Debug.Assert(0 <= start && start <= src.m_lastIndex);
			Debug.Assert(0 <= stop  && stop  <= src.m_lastIndex);
			Debug.Assert(m_lastIndex + stop - start + 1 < MaxIndex()); // full-node check
			for (int i = start; i <= stop; ++i)
				SetItem(++m_lastIndex, src.GetItem(i));
		}

		public void Append(BTreeEntry obj, BTreeNode n)
		{
			// Never called from anywhere where it might fill up THIS.

			Debug.Assert(m_lastIndex < MaxIndex());
			SetItem(++m_lastIndex, obj, n);
		}

		public void Append(BTreeItem itm)
		{
			Debug.Assert(m_lastIndex < MaxIndex());
			SetItem(++m_lastIndex, itm);
		}

		public void ShiftLeft(int cnt)
		{
			if (cnt <= 0)
				return;
			for (int i = cnt; i <= m_lastIndex; ++i)
				m_items[i-cnt] = new BTreeItem(GetItem(i));
			m_lastIndex -= cnt;
		}

		public int Psize()  { return m_lastIndex; }
		public int Vsize()
		{
			Debug.Assert(m_parentNode!= null && m_parentNode.GetTree(0) != this);
			return Psize()+1;
		}

		public int MaxIndex()  { return m_parentTree.m_innerMaxIndex; }
		public int MaxPsize()  { return m_parentTree.m_innerMaxIndex; }

		public bool IsFull()  { return m_lastIndex == MaxIndex(); }
		public void IsFull(BTreeNode that)
		{
			// The child node THAT is full. We will either redistribute elements
			// or create a new node and then redistribute.
			// In an attempt to minimize the number of splits, we adopt the following
			// strategy:
			//  * redistribute if possible
			//  * if not possible, then split with a sibling

			if (that.IsLeaf) 
			{
				BTreeLeafNode leaf = (BTreeLeafNode)that;
				BTreeLeafNode left = null;
				BTreeLeafNode right= null;
				// split LEAF only if both sibling nodes are full.
				int leafidx = IndexOf(leaf);
				bool hasRightSib = (leafidx < m_lastIndex) &&
					((right = (BTreeLeafNode)GetTree(leafidx+1)) != null);
				bool hasLeftSib  = (leafidx > 0) &&
					((left = (BTreeLeafNode)GetTree(leafidx-1)) != null);
				bool rightSibFull = (hasRightSib && right.IsAlmostFull());
				bool leftSibFull  = (hasLeftSib  && left.IsAlmostFull());
				if (rightSibFull) 
				{
					if (leftSibFull) 
					{
						// both full, so pick one to split with
						left.SplitWith(leaf, leafidx);
					} 
					else if (hasLeftSib) 
					{
						// left sib not full, so balance with it
						leaf.BalanceWithLeft(left, leafidx);
					} 
					else 
					{
						// there is no left sibling, so split with right
						leaf.SplitWith(right, leafidx+1);
					}
				} 
				else if (hasRightSib) 
				{
					// right sib not full, so balance with it
					leaf.BalanceWithRight(right, leafidx+1);
				} 
				else if (leftSibFull) 
				{
					// no right sib, and left sib is full, so split with it
					left.SplitWith(leaf, leafidx);
				} 
				else if (hasLeftSib) 
				{
					// left sib not full so balance with it
					leaf.BalanceWithLeft(left, leafidx);
				} 
				else 
					throw new BTreeException("neither a left or right sib; should never happen");
			} 
			else 
			{
				BTreeInnerNode inner = (BTreeInnerNode)that;
				// split INNER only if both sibling nodes are full
				int inneridx = IndexOf(inner);
				BTreeInnerNode left = null;
				BTreeInnerNode right= null;
				bool hasRightSib = (inneridx < m_lastIndex) &&
					((right = (BTreeInnerNode)GetTree(inneridx+1)) != null);
				bool hasLeftSib  = (inneridx > 0) &&
					((left=(BTreeInnerNode)GetTree(inneridx-1)) != null);
				bool rightSibFull = (hasRightSib && right.IsAlmostFull());
				bool leftSibFull  = (hasLeftSib  && left.IsAlmostFull());
				if (rightSibFull) 
				{
					if (leftSibFull) 
					{
						left.SplitWith(inner, inneridx);
					} 
					else if (hasLeftSib) 
					{
						inner.BalanceWithLeft(left, inneridx);
					} 
					else 
					{
						// there is no left sibling
						inner.SplitWith(right, inneridx+1);
					}
				} 
				else if (hasRightSib) 
				{
					inner.BalanceWithRight(right, inneridx+1);
				} 
				else if (leftSibFull) 
				{
					left.SplitWith(inner, inneridx);
				} 
				else if (hasLeftSib) 
				{
					inner.BalanceWithLeft(left, inneridx);
				} 
				else 
					throw new BTreeException("neither a left or right sib; should never happen");
			}
		}

		public bool IsAlmostFull()  { return m_lastIndex >= MaxIndex() - 1; }
		public bool IsLow()  {  return m_lastIndex < m_parentTree.m_innerLowWaterMark; }
		public void IsLow(BTreeNode that)
		{
			// The child node THAT is <= half full. We will either redistribute
			// elements between children, or THAT will be merged with another child.
			// In an attempt to minimize the number of mergers, we adopt the following
			// strategy:
			//  * redistribute if possible
			//  * if not possible, then merge with a sibling

			if (that.IsLeaf) 
			{
				BTreeLeafNode leaf = (BTreeLeafNode)that;
				BTreeLeafNode left = null;
				BTreeLeafNode right= null;
				// split LEAF only if both sibling nodes are full.
				int leafidx = IndexOf(leaf);
				bool hasRightSib = (leafidx < m_lastIndex) &&
					((right = (BTreeLeafNode)GetTree(leafidx+1)) != null);
				bool hasLeftSib  = (leafidx > 0) &&
					((left = (BTreeLeafNode)GetTree(leafidx-1)) != null);
				if (hasRightSib && (leaf.Psize() + right.Vsize()) >= leaf.MaxPsize()) 
				{
					// then cannot merge,
					// and balancing this and rightsib will leave them both
					// more than half full
					leaf.BalanceWith(right, leafidx+1);
				} 
				else if (hasLeftSib && (leaf.Vsize() + left.Psize()) >= leaf.MaxPsize()) 
				{
					// ditto
					left.BalanceWith(leaf, leafidx);
				} 
				else if (hasLeftSib) 
				{
					// then they should be merged
					left.MergeWithRight(leaf, leafidx);
				} 
				else if (hasRightSib) 
				{
					leaf.MergeWithRight(right, leafidx+1);
				} 
				else 
					throw new BTreeException("Not right or left sibling- should never happen");
			} 
			else 
			{
				BTreeInnerNode inner = (BTreeInnerNode)that;

				int inneridx = IndexOf(inner);
				BTreeInnerNode left = null;
				BTreeInnerNode right= null;
				bool hasRightSib = (inneridx < m_lastIndex) &&
					((right = (BTreeInnerNode)GetTree(inneridx+1)) != null);
				bool hasLeftSib  = (inneridx > 0) &&
					((left = (BTreeInnerNode)GetTree(inneridx-1)) != null);
				if (hasRightSib && (inner.Psize() + right.Vsize()) >= inner.MaxPsize()) 
				{
					// cannot merge
					inner.BalanceWith(right, inneridx+1);
				} 
				else if (hasLeftSib && (inner.Vsize() + left.Psize()) >= inner.MaxPsize()) 
				{
					// cannot merge
					left.BalanceWith(inner, inneridx);
				} 
				else if (hasLeftSib) 
				{
					left.MergeWithRight(inner, inneridx);
				} 
				else if (hasRightSib) 
				{
					inner.MergeWithRight(right, inneridx+1);
				} 
				else 
					throw new BTreeException("Not right or left sibling- should never happen");
			}
		}
	}

	[Serializable]
	class BTreeLeafNode : BTreeNode
	{
		internal BTreeEntry[] m_items;

		public BTreeLeafNode(BTreeInnerNode p, BTreeEntry item, BTree t)
			:base(p, t)
		{
			m_items = new BTreeEntry[MaxIndex()+1];
			if(item != null)
				m_items[++m_lastIndex] = item;
		}

		public override bool IsLeaf{get{return true;}}

		public override void Add(BTreeEntry obj, int index)
		{
			Add(obj, index, false);
		}

		public override void Add(BTreeEntry obj, int index, bool replaceAtIndex)
		{
			// Add the object OBJ to the leaf node, inserting it at location INDEX
			// in the m_items array.

			if(!replaceAtIndex)
			{
				Debug.Assert(0 <= index && index <= m_lastIndex+1);
				Debug.Assert(m_lastIndex <= MaxIndex());
				for (int i = m_lastIndex+1; i > index ; --i)
					m_items[i] = m_items[i-1];
				m_items[index] = obj;
				++m_lastIndex;

				// check for overflow
				if (m_parentNode == null)
					m_parentTree.IncrCount();
				else
					m_parentNode.IncrCount(this);

				if (IsFull()) 
				{
					// it's full; tell parent node
					if (m_parentNode == null) 
					{
						// this occurs when this leaf is the only node in the
						// btree, and this.m_parentTree.m_rootNode == this
						Debug.Assert(m_parentTree.m_rootNode == this);
						// in which case we inform the btree, which can be
						// considered the parent of this node
						m_parentTree.RootIsFull();
					} 
					else 
					{
						// the parent is responsible for splitting/balancing subnodes
						m_parentNode.IsFull(this);
					}
				}
			}
			else //do a simple replace
				m_items[index] = obj;
		}

		public override void Remove(int index)
		{
			Debug.Assert(index >= 0 && index <= m_lastIndex);
			for (int to = index; to < m_lastIndex; ++to)
				m_items[to] = m_items[to+1];
			--m_lastIndex;
			if (m_parentNode == null)
				m_parentTree.DecrCount();
			else
				m_parentNode.DecrCount(this);
			if (IsLow()) 
			{
				if (m_parentNode == null) 
				{
					// then this is the root; when no keys left, inform the tree
					if (Psize() == 0)
						m_parentTree.RootIsEmpty();
				} 
				else
					m_parentNode.IsLow(this);
			}
		}

		public void RemoveItem(int idx) { Remove(idx); }

		public override BTreeEntry this[int i]
		{
			get
			{
				if(!(i >= 0 && i <= m_lastIndex))
					throw new BTreeException(String.Format("Index({0}) of out range({1})", i, m_lastIndex));
				return m_items[i];
			}
		}

		public override object Found(IComparable key, ref BTreeNode which, ref int where)
		{
			// key was not in any inner node; it is either here, or it's
			// not in the tree.

			for (int i = 0; i <= m_lastIndex; ++i) 
			{
				if(m_items[i] != null)
				{
					int cmp = m_items[i].Key.CompareTo(key);
					if (cmp == 0) 
					{
						which = this;
						where = i;
						return m_items[i].Value;
					}
					//if (((IComparable)m_items[i].Key).CompareTo(key) > 0) 
					if(cmp > 0)
					{
						which = this;
						where = i;
						return null;
					}
				}
				else
					break;
			}
			which = this;
			where = m_lastIndex+1;
			return null;
		}

		public override bool Contains(IComparable key, ref BTreeNode which, ref int where)
		{
			// WHAT was not in any inner node; it is either here, or it's
			// not in the tree.

			for (int i = 0; i <= m_lastIndex; ++i) 
			{
				if(m_items[i] != null)
				{
					int cmp = m_items[i].Key.CompareTo(key);
					if (cmp == 0) 
					{
						which = this;
						where = i;
						return true;
					}
					//if (((IComparable)m_items[i].Key).CompareTo(key) > 0) 
					if(cmp > 0)
					{
						which = this;
						where = i;
						return false;
					}
				}
				else
					break;
			}
			which = this;
			where = m_lastIndex+1;
			return false;
		}

		public int Count(int i)
		{
			return 1;
		}

		public override int Count()
		{
			return Psize();
		}

		public override int FindRank(IComparable key, bool useClosestMatch)
		{
			// WHAT was not in any inner node; it is either here, or it's
			// not in the tree.

			for (int i = 0; i <= m_lastIndex; ++i) 
			{
				int cmp=-1;
				if (m_items[i].Key == null)
					cmp=-1;
				else
				try{
					cmp = m_items[i].Key.CompareTo(key);
					}catch(Exception e)
					{
						//Continue looking.  Couldnt convert type to compare to, so they are not equal.
					}
				if (cmp == 0)
					return i;
				//if (((IComparable)m_items[i].Key).CompareTo(key) > 0)
				if(cmp > 0)
					return useClosestMatch?i:-1;
			}
			return -1;
		}

		public override BTreeEntry GetKey(int idx) { return m_items[idx]; }
		public void SetKey(int idx, BTreeEntry obj) { m_items[idx] = obj; }

		public int IndexOf(object val)
		{
			// Returns a number in the range 0 to MaxIndex().

			for (int i = 0; i <= m_lastIndex; ++i) 
			{
				if (m_items[i].Value == val)
					return i;
			}
			return -1;
		}

		public override BTreeLeafNode  FirstLeafNode()
		{
			return this;
		}

		public override BTreeLeafNode  LastLeafNode()
		{
			return this;
		}

		public override void Split()
		{
			// This function is called only when THIS is the only descendent
			// of the root node, and THIS needs to be split.
			// Assumes that idx of THIS in Parent is 0.

			BTreeLeafNode newnode = new BTreeLeafNode(m_parentNode, null, null);
			m_parentNode.Append(m_items[m_lastIndex--], newnode);
			m_parentNode.SetCount(0, m_parentNode.GetTree(0).Count());
			m_parentNode.SetCount(1, m_parentNode.GetTree(1).Count());
			BalanceWithRight(newnode, 1);
		}

		public void SplitWith(BTreeLeafNode rightsib, int keyidx)
		{
			//m_parentTree.validateAllParentage();
			Debug.Assert(m_parentNode == rightsib.m_parentNode);
			Debug.Assert(keyidx > 0 && keyidx <= m_parentNode.m_lastIndex);
			int Count      = Psize() + rightsib.Vsize();
			int newSizeThis  = Count / 3;
			int newSizeNew   = (Count - newSizeThis) / 2;
			int newSizeSib   = (Count - newSizeThis - newSizeNew);
			int noFromThis   = Psize() - newSizeThis;
			int noFromSib    = rightsib.Vsize() - newSizeSib;
			Debug.Assert(noFromThis >= 0);
			Debug.Assert(noFromSib >= 1);
			BTreeLeafNode newNode  = new BTreeLeafNode(m_parentNode,null,null);
			m_parentNode.AddElt(keyidx, m_items[m_lastIndex--], newNode);
			m_parentNode.SetCount(keyidx, 0);
			m_parentNode.DecCount(keyidx-1,1);
			this.PushRight(noFromThis-1, newNode, keyidx);
			rightsib.PushLeft(noFromSib, newNode, keyidx+1);
			//m_parentTree.validateAllParentage();
			if (m_parentNode.IsFull())
				m_parentNode.InformParent();
			//m_parentTree.validateAllParentage();
		}

		public void MergeWithRight(BTreeLeafNode rightsib, int pidx)
		{
			Debug.Assert(Psize() + rightsib.Vsize() < MaxPsize());
			rightsib.PushLeft(rightsib.Psize(), this, pidx);
			Append(m_parentNode.GetKey(pidx));
			m_parentNode.SetCount(pidx-1, Count());
			m_parentNode.RemoveItem(pidx);
		}

		public void BalanceWithLeft(BTreeLeafNode leftsib, int pidx)
		{
			// THIS has more than LEFTSIB;  move some items from THIS to LEFTSIB.

			Debug.Assert(Vsize() >= leftsib.Psize());
			int newThisSize = (Vsize() + leftsib.Psize())/2;
			int noFromThis  = Psize() - newThisSize;
			PushLeft(noFromThis, leftsib, pidx);
		}

		public void BalanceWithRight(BTreeLeafNode rightsib, int pidx)
		{
			// THIS has more than RIGHTSIB;  move some items from THIS to RIGHTSIB.

			Debug.Assert(Psize() >= rightsib.Vsize());
			int newThisSize = (Psize() + rightsib.Vsize())/2;
			int noFromThis  = Psize() - newThisSize;
			PushRight(noFromThis, rightsib, pidx);
		}

		public void BalanceWith(BTreeLeafNode rightsib, int pidx)
		{
			// PITEM is the parent item whose key will change when keys are shifted
			// from one LeafNode to the other.

			if (Psize() < rightsib.Vsize())
				rightsib.BalanceWithLeft(this, pidx);
			else
				BalanceWithRight(rightsib, pidx);
		}

		public void PushLeft(int noFromThis, BTreeLeafNode leftsib, int pidx)
		{
			// noFromThis==1 => moves the parent item into the leftsib,
			// and the first item in this's array into the parent item.
			//m_parentTree.validateAllParentage();

			Debug.Assert(noFromThis > 0 && noFromThis <= Psize());
			Debug.Assert(noFromThis + leftsib.Psize() < MaxPsize());
			Debug.Assert(m_parentNode.GetTree(pidx) == this);
			leftsib.Append(m_parentNode.GetKey(pidx));
			if (noFromThis > 1)
				leftsib.AppendFrom(this, 0, noFromThis-2);
			m_parentNode.SetKey(pidx, m_items[noFromThis-1]);
			ShiftLeft(noFromThis);
			m_parentNode.SetCount(pidx-1, leftsib.Count());
			m_parentNode.SetCount(pidx, Count());
			//m_parentTree.validateAllParentage();
		}

		public void PushRight(int noFromThis, BTreeLeafNode rightsib, int pidx)
		{
			//m_parentTree.validateAllParentage();
			// noFromThis==1 => moves the parent item into the
			// rightsib, and the last item in this's array into the parent
			// item.

			Debug.Assert(noFromThis > 0 && noFromThis <= Psize());
			Debug.Assert(noFromThis + rightsib.Psize() < MaxPsize());
			Debug.Assert(m_parentNode.GetTree(pidx) == rightsib);
			// The operation is five steps:
			//  Step I.   Make room for the incoming keys in RIGHTSIB.
			//  Step II.  Move the key in the parent into RIGHTSIB.
			//  Step III. Move the items from THIS into RIGHTSIB.
			//  Step IV.  Move the item from THIS into the parent.
			//  Step V.   Update the length of THIS.
			//
			// Step I.: make space for noFromThis items
			//
			int start = m_lastIndex - noFromThis + 1;
			int tgt, src;
			tgt = rightsib.m_lastIndex + noFromThis;
			src = rightsib.m_lastIndex;
			rightsib.m_lastIndex = tgt;
			while (src >= 0)
				rightsib.m_items[tgt--] = rightsib.m_items[src--];

			// Step II. Move the key from the parent into place
			rightsib.m_items[tgt--] = m_parentNode.GetKey(pidx);

			// Step III.Move the items from THIS into RIGHTSIB
			for (int i = m_lastIndex; i > start; i--)
				rightsib.m_items[tgt--] = m_items[i];
			Debug.Assert(tgt == -1);

			// Step IV.
			m_parentNode.SetKey(pidx, m_items[start]);

			// Step V.
			m_lastIndex -= noFromThis;

			// Step VI.  update Count
			m_parentNode.SetCount(pidx-1, Count());
			m_parentNode.SetCount(pidx, rightsib.Count());
			m_parentNode.validateParentage();
			//m_parentTree.validateAllParentage();
		}

		public void AppendFrom(BTreeLeafNode src, int start, int stop)
		{
			// A convenience function, does not worry about the element in
			// the parent, simply moves elements from SRC[start] to SRC[stop]
			// into the current array.
			// This should never create a full node.
			// That is, it is not used anywhere where THIS could possibly be
			// near full.
			// Does NOT handle Count.

			if (start > stop)
				return;
			Debug.Assert(0 <= start && start <= src.m_lastIndex);
			Debug.Assert(0 <= stop  && stop  <= src.m_lastIndex);
			Debug.Assert(m_lastIndex + stop - start + 1 < MaxIndex()); // full-node check
			for (int i = start; i <= stop; ++i)
				m_items[++m_lastIndex] = src.m_items[i];
			Debug.Assert(m_lastIndex < MaxIndex());
		}

		public void Append(BTreeEntry obj)
		{
			// Never called from anywhere where it might fill up THIS
			// does NOT handle Count.

			m_items[++m_lastIndex] = obj;
			Debug.Assert(m_lastIndex < MaxIndex());
		}

		public void ShiftLeft(int cnt)
		{
			if (cnt <= 0)
				return;
			for (int i = cnt; i <= m_lastIndex; ++i)
				m_items[i-cnt] = m_items[i];
			m_lastIndex -= cnt;
		}

		public int Psize() { return m_lastIndex + 1; }
		public int Vsize()
		{
			Debug.Assert(m_parentNode != null);// && m_parentNode.GetTree(0) != this);
			return Psize()+1;
		}

		public int MaxIndex() { return m_parentTree.m_leafMaxIndex; }
		public int MaxPsize() { return m_parentTree.m_leafMaxIndex + 1; }
		public bool IsFull() { return m_lastIndex == MaxIndex(); }
		public bool IsAlmostFull() { return m_lastIndex >= MaxIndex() - 1; }
		public bool IsLow() { return m_lastIndex < m_parentTree.m_leafLowWaterMark; }
	}

	[Serializable]
	public class BTreeIterator
	{
		private BTree m_parentTree;      //btree being iterated
		private int m_treeIndex;    //current position in btree
		private bool m_movingForward; //iteration direction

		public BTreeIterator(BTree t, bool moveForward)
		{
			m_parentTree = t;
			m_treeIndex = -1;
			m_movingForward = moveForward;
			Reset();
		}

		public BTreeIterator(BTreeIterator iter)
		{
			// Copy ctor.
			m_parentTree  = iter.m_parentTree;
			m_treeIndex  = iter.m_treeIndex;
			m_movingForward = iter.m_movingForward;
		}

		public BTree SourceTree {get{ return m_parentTree; }}

		public bool Next()
		{
			if (m_movingForward) 
			{
				if (m_treeIndex < m_parentTree.Count-1)
				{
					++m_treeIndex;
					return true;
				}
			} 
			else 
			{
				if (m_treeIndex > 0)
				{
					--m_treeIndex;
					return true;
				}
			}
			return false;
		}

		public BTreeEntry CurrentElement 
		{
			get
			{
				if(m_treeIndex >=0 && m_treeIndex < m_parentTree.Count)
					return m_parentTree[m_treeIndex];
				return null;
			}
		}

		public void MoveToClosest(IComparable key)
		{
			int r = m_parentTree.Rank(key, true);
			if(r >= 0)
				m_treeIndex = r;
		}

		public void Reset()
		{
			// Reset the B-tree iterator.

			if (m_movingForward)
				m_treeIndex = -1;
			else
				m_treeIndex = m_parentTree.Count - 1;
		}
	}
}
